1. Technical Field
The invention relates to digital computing devices for computing in real time a sum of terms of the form: EQU .SIGMA.h(iT).qe((n-i)T
in which
T designates a sampling period, PA0 h(iT) are coefficients, and PA0 qe are the estimated values of transmitted data qe, which may take on the values -3, -1, +3 and +1.
2. Prior Art
The problem of computing such a sum arises particularly in the construction of linear filters used in echo cancellers (which will be designated hereafter by the usual abbreviation ECC) for an installation for digital transmission of data using code 2B 1Q. This code is likely to be adapted as a standard following standardization of the U-interface in the United States of America. It associates with each set of two bits, called "dibit", one level among four, in accordance with the following table:
______________________________________ dibit transmitted level ______________________________________ 00 -3 01 -1 10 +3 11 +1 ______________________________________
The data qe(t) transmitted on line may consequently assume the four above values. In a transmission installation whose channel has a pulse response h(t), the signal sr(nT) received at time nT is: ##EQU1##
Search for the estimated values qe of qe involves, in a reception apparatus, computation of sums of the form (1). For example, whenever the transmission lines are heterogenous, the decision concerning the value of qe(nT) can only be made after subtracting, from the received signal sr(nT), an estimation of the intersymbol interference, or ISI, whose exact value would be: ##EQU2##
Estimation is conventionally made by means of an adaptive recursive equalizer with decision within the loop, frequently designated by the abbrevation DFE, with N coefficients, which computes the term Tr(nT): ##EQU3## where h(iT) is the nth coefficient stored in the and is an estimate of the nth sample of the pulse response h(t).
The digital computation of Tr(nT) involves, if formula (2) is applied: EQU N multiplications h(iT)*qe((n-i)T), and EQU N additions
Taking into account that the estimated data qe may only assume values +3, +1, -3 and -1 and is therefor coded over two bits, each multiplication can be broken down into two additions and a shift: the operation 3* h(iT) becomes for example: EQU h(iT))+2* h(iT)
While by using this transformation, a computing device devoid of multiplier may be used, the computing time is doubled since it requires 2N cycles rather than N cycles.
It is an object of the invention to provide a device which neither requires a multiplier, nor substantially lengthens the computing time. For that, it start from a complete analysis of the transmission channel and of its components with the purpose of modify equation (2) (or the corresponding equation in the case of an ECC), into a form comprising terms which may be neglected without undesirable consequences.
A first step consists in introducing a variable qde=1+qe which, because qe can take the values +3, +1, -3, -1, can only take the values +4, +2, -2, 0 which are powers of 2. The equation (2) which gives Tr(nT) becomes, depending on the values qde((n-1)T): ##EQU4## which may also be written: ##EQU5##
The second term of equation (4) may be transformed since the transmission channel stops the DC component of the signal and consequently the overall gain of the channel ##EQU6## for the DC component is zero. That overall gain may be written as: ##EQU7##
Furthermore, the term ##EQU8## may be neglected, for in a DFE having N coefficients it is accepted that the value of the "drag" beyond NT need not be taken into consideration. Equation (5) then shows that ##EQU9## may be replaced in (4) with h(0). The equation (4) then becomes: ##EQU10##
Since qde is always a power of 2, computation of the first term of the equation (6) only involves N additions and possibly shifts, depending on the value of qde. Adding the second term lengthens computation by one computing cycle only. N+1 cycles are sufficient, instead of 2N cycles in the case of equation (2).
There is consequently provided a computing device comprising: means for transforming values qe into values qde which are powers of 2, by addition (or subtraction) of the same number from all the values; means for computing the elementary products obtained by possible shifts of h depending on the value of qde; means for summing the elementary products and means for possibly adding them to a constant forming an evaluation of the difference in result due to the variable change.
In the above-mentioned case in which the device forms an adaptative recursive equalizer operating in accordance with the equation (6), the constant value constitutes an evaluation h(0) of the first term of the transfer function. The values h may be continuously adapted by a network of known type, using for example the gradient algorithm or the sign algorithm.
In the case where the device is to be used as echo canceller, the synthetized echo Ec(nT) is obtained by a formula similar to equation (2), using N estimated coefficients which will be designated g(iT). ##EQU11## with qe=+3, +1, -1 or -3.
Here again, for computing Ec(nT) using this formula, 2N computing cycles would be necessary if multiplications are to be avoided.
A device according to the invention effects a change of variable on the transmitted data qe: EQU qde((n-i)T)=1+qe((n-i)T)
then qde can only assume values +4, +2, 0 and -2. The echo may be written as: ##EQU12##
The second term of the equation may be replaced with: ##EQU13## for the gain of the echo channel at a zero frequency ##EQU14## is zero; in an echo canceller of length NT, it may be assumed that the echo energy is zero beyond NT, therefore that ##EQU15##
The echo Ec(nT) is therefore limited to the first term of equation (4 bis), i.e.: ##EQU16##
A parameter q'de(i) may be introduced: EQU q'de(i)=1/2 qde(i)
and then q'de(i) may only assume the values -1, 0, 1 or 2; and, if coefficients g'(i)=2 g(i) are used, equation (6 bis) may be written: ##EQU17##
Thus it can be seen that, provided values which are double of the ECC coefficients are stored, the mathematical products which intervene in the sum may be substituted with:
generation of a zero for qde=0,
transparency (equality of the output and of the input with possible sign change) for qde=2 or -2,
shift of a bit towards the most significant bits for qde=4.
The invention will be better understood from the following description of a particular embodiment, given by way of example, and from the comparison which is made with a known device. The description refers to the accompanying drawings.